package.cpath = package.cpath .. ';C:/Users/win/AppData/Roaming/JetBrains/IdeaIC2020.3/plugins/intellij-emmylua/classes/debugger/emmy/windows/x86/?.dll'
local dbg = require('emmy_core')
dbg.tcpConnect('localhost', 9966)

package.path = package.path .. ";C:/Users/win/Documents/_lua/util/?.lua"

local BRTree = require("BRTree")


function TestAdd1()
    local t = BRTree.new(function(a, b)
        return a - b
    end)
    assert(0 == t:GetCount())
    assert(false == t:Contains(0))

    t:Add(275)
    assert(1 == t:GetCount())
    assert(false == t:Contains(0))
    assert(true == t:Contains(275))
    assert("(275)" == tostring(t))

    t:Add(711)
    assert(2 == t:GetCount())
    assert(false == t:Contains(0))
    assert(true == t:Contains(711))
    assert("(275),711" == tostring(t))

    t:Add(260)
    assert(3 == t:GetCount())
    assert(false == t:Contains(0))
    assert(true == t:Contains(260))
    assert("(275),260,711" == tostring(t))

    t:Add(515)
    assert(4 == t:GetCount())
    assert(false == t:Contains(0))
    assert(true == t:Contains(515))
    assert("(275),(260),(711),515" == tostring(t))

    t:Add(442)
    assert(5 == t:GetCount())
    assert(false == t:Contains(0))
    assert(true == t:Contains(442))
    assert("(275),(260),(515),442,711" == tostring(t))

    t:Add(800)
    assert(6 == t:GetCount())
    assert(false == t:Contains(0))
    assert(true == t:Contains(800))
    assert("(275),(260),515,(442),(711),800" == tostring(t))

    t:Add(900)
    assert(7 == t:GetCount())
    assert(false == t:Contains(0))
    assert(true == t:Contains(900))
    assert("(275),(260),515,(442),(800),711,900" == tostring(t))

    t:Add(50)
    assert(8 == t:GetCount())
    assert(false == t:Contains(0))
    assert(true == t:Contains(50))
    assert("(275),(260),515,50,(442),(800),711,900" == tostring(t))

    t:Add(270)
    assert(9 == t:GetCount())
    assert(false == t:Contains(0))
    assert(true == t:Contains(270))
    assert("(275),(260),515,50,270,(442),(800),711,900" == tostring(t))

    t:Add(20)
    assert(10 == t:GetCount())
    assert(false == t:Contains(0))
    assert(true == t:Contains(20))
    assert("(275),260,515,(50),(270),(442),(800),20,711,900" == tostring(t))

    t:Add(30)
    assert(11 == t:GetCount())
    assert(false == t:Contains(0))
    assert(true == t:Contains(30))
    assert("(275),260,515,(30),(270),(442),(800),20,50,711,900" == tostring(t))
end
TestAdd1()



function TestAdd2()
    local t = BRTree.new(function(a, b)
        return a - b
    end)

    t:Add(12)
    assert(1 == t:GetCount())
    assert(false == t:Contains(0))
    assert(true == t:Contains(12))
    assert("(12)" == tostring(t))

    t:Add(1)
    assert(2 == t:GetCount())
    assert(false == t:Contains(0))
    assert(true == t:Contains(1))
    assert("(12),1" == tostring(t))

    t:Add(9)
    assert(3 == t:GetCount())
    assert(false == t:Contains(0))
    assert(true == t:Contains(9))
    assert("(9),1,12" == tostring(t))

    t:Add(2)
    assert(4 == t:GetCount())
    assert(false == t:Contains(0))
    assert(true == t:Contains(2))
    assert("(9),(1),(12),2" == tostring(t))

    t:Add(0)
    assert(5 == t:GetCount())
    assert(false == t:Contains(-1))
    assert(true == t:Contains(0))
    assert("(9),(1),(12),0,2" == tostring(t))

    t:Add(11)
    assert(6 == t:GetCount())
    assert(false == t:Contains(-1))
    assert(true == t:Contains(11))
    assert("(9),(1),(12),0,2,11" == tostring(t))

    t:Add(7)
    assert(7 == t:GetCount())
    assert(false == t:Contains(-1))
    assert(true == t:Contains(11))
    assert("(9),1,(12),(0),(2),11,7" == tostring(t))

    t:Add(19)
    assert(8 == t:GetCount())
    assert(false == t:Contains(-1))
    assert(true == t:Contains(19))
    assert("(9),1,(12),(0),(2),11,19,7" == tostring(t))

    t:Add(4)
    assert(9 == t:GetCount())
    assert(false == t:Contains(-1))
    assert(true == t:Contains(4))
    assert("(9),1,(12),(0),(4),11,19,2,7" == tostring(t))

    t:Add(15)
    assert(10 == t:GetCount())
    assert(false == t:Contains(-1))
    assert(true == t:Contains(15))
    assert("(9),1,12,(0),(4),(11),(19),2,7,15" == tostring(t))

    t:Add(18)
    assert(11 == t:GetCount())
    assert(false == t:Contains(-1))
    assert(true == t:Contains(18))
    assert("(9),1,12,(0),(4),(11),(18),2,7,15,19" == tostring(t))

    t:Add(5)
    assert(12 == t:GetCount())
    assert(false == t:Contains(-1))
    assert(true == t:Contains(5))
    assert("(9),(1),(12),(0),4,(11),(18),(2),(7),15,19,5" == tostring(t))

    t:Add(14)
    assert(13 == t:GetCount())
    assert(false == t:Contains(-1))
    assert(true == t:Contains(14))
    assert("(9),(1),(12),(0),4,(11),18,(2),(7),(15),(19),5,14" == tostring(t))

    t:Add(13)
    assert(14 == t:GetCount())
    assert(false == t:Contains(-1))
    assert(true == t:Contains(13))
    assert("(9),(1),(12),(0),4,(11),18,(2),(7),(14),(19),5,13,15" == tostring(t))

    t:Add(10)
    assert(15 == t:GetCount())
    assert(false == t:Contains(-1))
    assert(true == t:Contains(10))
    assert("(9),(1),(12),(0),4,(11),18,(2),(7),10,(14),(19),5,13,15" == tostring(t))

    t:Add(16)
    assert(16 == t:GetCount())
    assert(false == t:Contains(-1))
    assert(true == t:Contains(16))
    assert("(9),(1),(14),(0),4,12,18,(2),(7),(11),(13),(15),(19),5,10,16" == tostring(t))

    t:Add(6)
    assert(17 == t:GetCount())
    assert(false == t:Contains(-1))
    assert(true == t:Contains(6))
    assert("(9),(1),(14),(0),4,12,18,(2),(6),(11),(13),(15),(19),5,7,10,16" == tostring(t))

    t:Add(3)
    assert(18 == t:GetCount())
    assert(false == t:Contains(-1))
    assert(true == t:Contains(3))
    assert("(9),(1),(14),(0),4,12,18,(2),(6),(11),(13),(15),(19),3,5,7,10,16" == tostring(t))

    t:Add(8)
    assert(19 == t:GetCount())
    assert(false == t:Contains(-1))
    assert(true == t:Contains(8))
    assert("(9),(4),(14),1,6,12,18,(0),(2),(5),(7),(11),(13),(15),(19),3,8,10,16" == tostring(t))

    t:Add(17)
    assert(20 == t:GetCount())
    assert(false == t:Contains(-1))
    assert(true == t:Contains(17))
    assert("(9),(4),(14),1,6,12,18,(0),(2),(5),(7),(11),(13),(16),(19),3,8,10,15,17" == tostring(t))

end
TestAdd2()


function TestDel2()
    local t = BRTree.new(function(a, b)
        return a - b
    end)
    t._noBlackRed = true
    local v = 9
    t:Add(v)
    t:_SetColor(v, true)
    v = 4
    t:Add(v)
    t:_SetColor(v, true)
    v = 14
    t:Add(v)
    t:_SetColor(v, true)
    v = 1
    t:Add(v)
    t:_SetColor(v, false)
    v = 6
    t:Add(v)
    t:_SetColor(v, false)
    v = 12
    t:Add(v)
    t:_SetColor(v, false)
    v = 18
    t:Add(v)
    t:_SetColor(v, false)
    v = 0
    t:Add(v)
    t:_SetColor(v, true)
    v = 2
    t:Add(v)
    t:_SetColor(v, true)
    v = 5
    t:Add(v)
    t:_SetColor(v, true)
    v = 7
    t:Add(v)
    t:_SetColor(v, true)
    v = 11
    t:Add(v)
    t:_SetColor(v, true)
    v = 13
    t:Add(v)
    t:_SetColor(v, true)
    v = 16
    t:Add(v)
    t:_SetColor(v, true)
    v = 19
    t:Add(v)
    t:_SetColor(v, true)
    v = 3
    t:Add(v)
    t:_SetColor(v, false)
    v = 8
    t:Add(v)
    t:_SetColor(v, false)
    v = 10
    t:Add(v)
    t:_SetColor(v, false)
    v = 15
    t:Add(v)
    t:_SetColor(v, false)
    v = 17
    t:Add(v)
    t:_SetColor(v, false)
    t._noBlackRed = false
    assert("(9),(4),(14),1,6,12,18,(0),(2),(5),(7),(11),(13),(16),(19),3,8,10,15,17" == tostring(t))
    assert(20 == t:GetCount())

    t:Remove(12)
    assert(19 == t:GetCount())
    assert(false == t:Contains(12))
    assert("(9),(4),(14),1,6,11,18,(0),(2),(5),(7),(10),(13),(16),(19),3,8,15,17" == tostring(t))

    t:Remove(1)
    assert(18 == t:GetCount())
    assert(false == t:Contains(1))
    assert("(9),(4),(14),2,6,11,18,(0),(3),(5),(7),(10),(13),(16),(19),8,15,17" == tostring(t))

    t:Remove(9)
    assert(17 == t:GetCount())
    assert(false == t:Contains(9))
    assert("(10),(4),(14),2,6,(11),18,(0),(3),(5),(7),13,(16),(19),8,15,17" == tostring(t))

    t:Remove(2)
    assert(16 == t:GetCount())
    assert(false == t:Contains(2))
    assert("(10),(4),(14),(3),6,(11),18,0,(5),(7),13,(16),(19),8,15,17" == tostring(t))

    t:Remove(0)
    assert(15 == t:GetCount())
    assert(false == t:Contains(0))
    assert("(10),(4),(14),(3),6,(11),18,(5),(7),13,(16),(19),8,15,17" == tostring(t))

    t:Remove(11)
    assert(14 == t:GetCount())
    assert(false == t:Contains(11))
    assert("(10),(4),(14),(3),6,(13),18,(5),(7),(16),(19),8,15,17" == tostring(t))

    t:Remove(7)
    assert(13 == t:GetCount())
    assert(false == t:Contains(7))
    assert("(10),(4),(14),(3),6,(13),18,(5),(8),(16),(19),15,17" == tostring(t))

    t:Remove(19)
    assert(12 == t:GetCount())
    assert(false == t:Contains(19))
    assert("(10),(4),(14),(3),6,(13),16,(5),(8),(15),(18),17" == tostring(t))

    t:Remove(4)
    assert(11 == t:GetCount())
    assert(false == t:Contains(4))
    assert("(10),(5),(14),(3),(6),(13),16,8,(15),(18),17" == tostring(t))

    t:Remove(15)
    assert(10 == t:GetCount())
    assert(false == t:Contains(15))
    assert("(10),(5),(14),(3),(6),(13),17,8,(16),(18)" == tostring(t))

    t:Remove(18)
    assert(9 == t:GetCount())
    assert(false == t:Contains(18))
    assert("(10),(5),(14),(3),(6),(13),(17),8,16" == tostring(t))

    t:Remove(5)
    assert(8 == t:GetCount())
    assert(false == t:Contains(5))
    assert("(10),(6),(14),(3),(8),(13),(17),16" == tostring(t))

    t:Remove(14)
    assert(7 == t:GetCount())
    assert(false == t:Contains(14))
    assert("(10),(6),(16),(3),(8),(13),(17)" == tostring(t))

    t:Remove(13)
    assert(6 == t:GetCount())
    assert(false == t:Contains(13))
    assert("(10),6,(16),(3),(8),17" == tostring(t))

    t:Remove(10)
    assert(5 == t:GetCount())
    assert(false == t:Contains(10))
    assert("(16),6,(17),(3),(8)" == tostring(t))

    t:Remove(16)
    assert(4 == t:GetCount())
    assert(false == t:Contains(16))
    assert("(6),(3),(17),8" == tostring(t))

    t:Remove(6)
    assert(3 == t:GetCount())
    assert(false == t:Contains(6))
    assert("(8),(3),(17)" == tostring(t))

    t:Remove(3)
    assert(2 == t:GetCount())
    assert(false == t:Contains(3))
    assert("(8),17" == tostring(t))

    t:Remove(8)
    assert(1 == t:GetCount())
    assert(false == t:Contains(8))
    assert("(17)" == tostring(t))

    t:Remove(17)
    assert(0 == t:GetCount())
    assert(false == t:Contains(17))
    assert("" == tostring(t))
end
TestDel2()

